import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdRandom;

public class Quick extends Example {
    private static int partition(Comparable[] a,int lo,int hi){
        int i = lo,j=hi+1;
        Comparable v = a[lo];
        while(true){
            while(less(a[++i],v));
            while(less(v,a[--j]));
            if(i>=j) break;
            exch(a,i,j);
        }
        exch(a,lo,j);
        return j;
    }
    public static void sort(Comparable[] a){
        //StdRandom.shuffle(a);
        sort(a,0,a.length-1);
    }
    private static void sort(Comparable[] a,int lo, int hi){
        if(hi<=lo) return;
        int j=partition(a,lo,hi);
        sort(a,lo,j-1);
        sort(a,j+1,hi);
    }
    public static void main(String[] args){
        String[] a = StdIn.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}
